265. Paint House II
Hard

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x k cost matrix costs.

  • For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on...

Return the minimum cost to paint all houses.

 

Example 1:

Input: costs = [[1,5,3],[2,9,4]]
Output: 5
Explanation:
Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; 
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

Example 2:

Input: costs = [[1,3],[2,4]]
Output: 5

 

Constraints:

  • costs.length == n
  • costs[i].length == k
  • 1 <= n <= 100
  • 1 <= k <= 20
  • 1 <= costs[i][j] <= 20

 

Follow up: Could you solve it in O(nk) runtime?

Accepted
71,036
Submissions
153,076
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.92 (49 votes)

Premium

Solution

Paint House II is a follow up question of Paint House. In the original Paint House problem, k was always 3. In this problem, k is no longer fixed and instead can be any non-negative integer.

If you haven't yet attempted the original Paint House question and are having trouble with this question, go attempt Paint House first and come back. There is also an in-depth Paint House Solution Article. This solution article will assume you are already comfortable with the memoization and dynamic programming solutions for Paint House.


Approach 1: Memoization

Intuition

Remembering that we already know how to solve this problem using memoization when k = 3 (check the Paint House Solution Article) if you can't remember how), let's think through some of the other possible values of k.

For this explanation, we'll call a way of painting the houses valid if, and only if, there are no adjacent houses painted the same color. We'll call an input valid if it is possible to paint the houses in a valid way. The test cases here on Leetcode are all valid inputs. In an interview however, you'd need to ensure that it is safe to assume that the input is always valid though.

If k = 0, then this means we have no colors. If there are no colors, it's probably reasonable to assume there are no houses either, i.e. n = 0. In other words, the input is []. For this question here on Leetcode, this is a safe assumption. In an interview though it could be a good idea to ask the interviewer whether or not the input is guaranteed to be valid. For example, could you get a test case such as [[],[],[],[]]? This would be k = 0 and n = 4. Of course, this case doesn't make much sense, because we are supposed to be painting houses, but can't with no paint. Either you'd be told it could never happen, or that you needed to do something special for it, such as returning -1.

If k = 1 (all houses have to be the same color), then it's probably safe to assume that n = 1. Otherwise, the problem would be impossible to solve without breaking the adjacent color rule. Again, this is a safe assumption here, but do consider asking the interviewer whether or not you could get an invalid input that had k = 1 and n > 1. So, assuming that k = 1 and n = 1, the total cost will be the cost of painting that one house the only color available.

If k = 2 (there are two colors), then we know the problem is always solvable, because we can simply paint the houses alternating colors. For example, when n = 5 and k = 2, here are the only 2 valid ways of painting the houses. Anything else would be invalid.

The only 2 ways of painting 5 houses with 2 colors.

The answer will be the one that leads to the lowest cost. It'd be easy to check both.

When k = 3, the problem is equivalent to Paint House. In the Solution Article for that question, we worked through an example where n = 4.

[[17, 2, 17], [8, 4, 10], [6, 3, 19], [4, 8, 12]]

A good way to visualize all of the valid painting permutations is to use a tree. Each root-to-leaf path represents one valid way of painting the houses.

A tree showing all the valid permutations.

The cheapest cost of painting the houses is, therefore, the root-to-leaf path with the lowest total sum of its nodes. This animation shows the algorithm we used to solve this problem for Paint House.

Current
1 / 27

Luckily, we didn't actually need to create the tree itself—there is a simpler way using recursion.

Say we have a paint function that takes 2 parameters: a house number and a color to paint that house. The output is the total cost of painting that house and all the ones after it. For example paint(1, red) would be the cost of painting house 1 red, along with the cost of painting the houses after it (taking into account restrictions caused by painting house 1 red).

Therefore the cheapest way of painting all the houses can be expressed as follows, where 0 is the first house.

min(paint(0, "red"), paint(0, "green"), paint(0, "blue"))

The paint function has a recursive implementation. costs refers to the input table.

def paint(i, color):
    ### BASE CASE ###
    if i is the last house number:
        return costs[i][color]
    ### RECURSIVE CASE ###
    lowest_cost = Infinity
    for each next_color in ["red", "green", "blue"]:
       if next_color != color: # No adjacent houses can be same color.
           this_cost = costs[i][color] + paint(i + 1, next_color) # <- Recursive call
           lowest_cost = min(lowest_cost, this_cost)
    return lowest_cost

The base case is where i refers to the last house. Painting the last house a particular color can be obtained from the costs table.

The recursive case is where we also need to consider the houses after i. It is obtained by looking up the cost of painting house i the given color (in the costs table) and then by determining the cost of painting the houses after it. The cost of painting the houses after requires making recursive paint calls to determine the cost of painting house i + 1 each of the 2 other colors and then finding the minimum of those 2 values.

This algorithm is inefficient though. There is a lot of repetition in the tree, meaning we're doing the same calculations over and over again. For example, the total cost of painting the second house blue will be the same regardless of whether the first house was red or green. For example, both these branches of the tree are identical.

Repetition in the tree.

This should also be apparent from the definition of the paint function. The parameters are simply a house number and a color. It doesn't require any information about where exactly in the tree it is.

To solve this problem, we add memoization to the paint function. Recall that memoization is where before returning an answer, the recursive function writes the answer into a dictionary with the input parameters as the key and the answer as the value. Then before doing a calculation, it checks whether or not that particular calculation has already been done. For the example above, the function would only calculate the cost of painting the second house blue once, and then the second time it would look it up in the dictionary.

Here is a visualization that shows the calculations that need to be done when using memoization. The brighter circles show where the function body runs, and the duller circles show where a lookup was done and the function immediately returned. These are the only times the function is called.

A visualization showing what recursive calls the memoization approach actually makes.

If this explanation wasn't thorough enough for you, then please check out the full Paint House Solution Article. In that article I go into a lot more depth about memoization and how this algorithm was derived.

The k > 3 case is really no different to this. The only difference is that instead of only considering 2 possible colors for the next house, we're considering k - 1 colors (all colors except for the color of the current house).

Algorithm

Unlike the pseudocode above, we don't need to worry about the names of the colors. Instead, they are represented by numbers between 0 and k - 1. Additionally, we're also using memoization (lru_cache in Python, and a dictionary in Java).

Complexity Analysis

  • Time complexity : O(nk2)O(n \cdot k ^ 2).

    Determining the total time complexity of a recursive memoization algorithm requires looking at how many calls are made to the paint function, and how much each call costs (remember that the memoization lookups are O(1)O(1)). The function is called once for each possible pair of house number and color. This gives nkn \cdot k calls. Then, each call has a loop that loops over each of the kk colors. Therefore, we have nkk=nk2n \cdot k \cdot k = n \cdot k ^2 which is O(nk2)O(n \cdot k ^ 2).

    The part outside of the recursive function is O(k)O(k) and therefore does not impact the overall complexity.

  • Space complexity : O(nk)O(n \cdot k).

    There are 2 different places memory is being used that we need to consider.

    Firstly, the memoization is storing the answers for each pair of house number and color. There are nkn \cdot k of these, and so O(nk)O(n \cdot k) memory used.

    Secondly, we need to consider the memory used on the run-time stack. In the worst case, there's a stack frame for each house number on the stack. This is a total of O(n)O(n).

    The O(n)O(n) is insignficant to the O(nk)O(n \cdot k), so we're left with a total of O(nk)O(n \cdot k).



Approach 2: Dynamic Programming

Intuition

Let's look at a bigger example now, and view the problem in a different way to how we did before. For this example, k = 6 and n = 5.

[[10, 6, 16, 25, 7, 28], [7, 16, 18, 30, 16, 25], [8, 26, 6, 22, 26, 19], [10, 23, 14, 17, 23, 9], [12, 14, 27, 7, 8, 9]]

And here is a diagram of the input grid.

A picture of the input grid.

Each row represents the different colors a house could be. Remember that the colors are represented by numbers. The actual colors are only to make the table easier to read.

The problem we're trying to solve is equivalent to the following: pick exactly one number from each row such that the sum of those numbers is minimized. Because 2 adjacent houses cannot be the same color, adjacent rows must be picked from different columns. This is a straightforward variant of one of those "classic" minimum-path-in-a-grid dynamic programming problems.

The way that we solve it is to iterate over the cells and determine what the cheapest way of getting to that cell is. We'll work from top to bottom.

To begin with, we say the first row (house 0) is already completed. We don't need to make any changes to it.

Then, for each cell in the second row, we work out the cheapest way of getting to it from the first row is. For example, to get to [1][red] we have to go through any of the non-red cells from the row above. We want to go through the minimum.

Choosing the best path to house 1, red.

We show our decision by updating [1][red] to 7 + 6 = 13.

We can repeat this for the rest of the second row, and then work down each of the remaining rows.

Here's an animation of the algorithm being carried out.

When we're finished, the final answer is the minimum value in the last row.

Algorithm

We'll do this in the same way we did in the animation above—an in-place algorithm that over-writes the input grid.

Complexity Analysis

  • Time complexity : O(nk2)O(n \cdot k ^ 2).

    We iterate over each of the nkn \cdot k cells. For each of the cells, we're finding the minimum of the kk values in the row above, excluding the one that is in the same column. This operation is O(k)O(k). Multiplying this out, we get O(nk2)O(n \cdot k ^ 2).

  • Space complexity : O(1)O(1) if done in-place, O(nk)O(n \cdot k) if input is copied.

    We're not creating any new data structures in the code above, and so it has a space complexity of O(1)O(1). This is, however, overwriting the given input, which might not be ideal in some situations.

    If we don't want to overwrite the input, we could instead create a copy of it first and then do the calculations in the copy. This will require an additional O(nk)O(n \cdot k) space.



Approach 3: Dynamic Programming with O(k) additional Space.

Intuition

Implementing the algorithm in-place meant that we only needed O(1)O(1) additional space. This, however required modifying the input, which could be a problem in some situations.

The easiest solution is to make a copy of the input array and then do the calculations in that instead. This would require O(nk)O(n \cdot k) additional space.

There is a way that uses less space though. We're only ever working with 2 rows at a time: the current row, and the row before it. The rows before that are never looked at again, and the rows after are still the same as the input array. Therefore, we can take advantage of this to only use O(k)O(k) space.

Algorithm

Instead of writing the updated costs into the input array, the algorithm writes them into a k-length array. The k-length array from the previous row is held onto in-order to do these calculations.

Complexity Analysis

  • Time complexity : O(nk2)O(n \cdot k ^ 2).

    Same as above.

  • Space complexity : O(k)O(k).

    The previous row and the current row are represented as k-length arrays.

    This approach does not modify the input grid.



Approach 4: Dynamic programming with Optimized Time

Intuition

Despite Paint House II being listed as a hard question, and the problem statement listing O(nk)O(n \cdot k) time as a "follow up", you'd possibly be expected to come up with this solution at top companies as it's still a fairly basic dynamic programming algorithm. You should, therefore, ensure you're comfortable with this approach and could identify and apply similar observations in other dynamic programming problems. At the very least, it'll make you look awesome!

So far, all of our approaches have had a O(nk2)O(n \cdot k^2) time complexity. This is because calculating the new value for each of the O(nk)O(n \cdot k) cells required looking at each of the kk cells in the row immediately below.

However, we don't need to look at the entire previous row for every cell. Let's look again at the large example from above. When we're calculating the values for the second row, we're adding the minimum from the first row onto them. The only cell we can't do this for is the one that was directly below the minimum, as this would break the adjacency rule. For this one, it makes sense to add the second minimum.

We're only ever adding 2 different numbers.

Here's an animation of the entire algorithm.

Current
1 / 14

Algorithm

The simplest way of implementing this algorithm is to base it on the animation above. This requires overwriting the input.

Complexity Analysis

  • Time complexity : O(nk)O(n \cdot k).

    The first loop that finds the minimums of the first row is O(k)O(k) because it looks at each of the kk values in the first row exactly once. The second loop is O(nk)O(n \cdot k) because the outer loop loops nn times, and the inner loop loops kk times. O(nk)+O(k)=O(nk)O(n \cdot k) + O(k) = O(n \cdot k). We know it is impossible to ever do better here, because we cannot solve the problem without at least looking at each of the nkn \cdot k cells once.

  • Space complexity : O(1)O(1).

    Like approach 2, this approach also modifies the input instead of allocating its own space.



Approach 5: Dynamic programming with Optimized Time and Space

Intuition

There is another way we can still solve the problem in O(1)O(1) space and O(nk)O(n \cdot k) time complexity, and preserving the input.

The only thing the algorithm in the previous approach is really doing is going through the rows, and finding the 2 minimums of each row. It does this by calculating all the new costs for the row, writing them into the input, and then finding the minimums. This overwriting isn't necessary though—we can simply keep track of the 2 smallest values we've seen so far, as we go, in the current row. We also need to remember the 2 from the previous row.

Algorithm

The approach is a hybrid of approach 3 and 4. Like approach 4, it finds the minimums once instead of repeatedly. Like approach 3, it keeps track of information only from the current and previous rows. Unlike approach 3 though, the only information kept is the minimums.

There are many ways to compact the code a bit more, particularly in the case of the Python. I haven't done this here as it could be problematic for those less familiar with the 2 languages I have provided solutions in, however feel free to post your own solutions in the comments. I'm excited to see the elegance you can come up with!

Complexity Analysis

  • Time complexity : O(nk)O(n \cdot k).

    Same as the previous approach.

  • Space complexity : O(1)O(1).

    The only additional working memory we're using is a constant number of single-value variables to keep track of the 2 minimums in the current and previous row, and to calculate the cost of the current cell. Because the memory usage is constant, we say it is O(1)O(1). Unlike the previous approach one though, this one does not overwrite the input.


Report Article Issue

Comments: 16
LIIIII's avatar
Read More

this question should not be marked 'hard'. people would think they can handle hard questions.

50
Show 3 replies
Reply
Share
Report
bobxu1128's avatar
Read More

wow. great article!

9
Reply
Share
Report
yz443's avatar
Read More

Same as problem 1289, minfallsum2

6
Reply
Share
Report
yunqu's avatar
Read More

There is no need for DP... Only keep the current smallest cost color and the 2nd smallest cost color.

3
Reply
Share
Report
patriciaharris's avatar
Read More

Thanks for the great explanation!
In Approach 2, line 16, the line should be - minor typo.

     costs[house][color] += min;

2
Reply
Share
Report
joanfanjack's avatar
Read More

met a similar on Google onsite, that one was 5% more complicated than this. But I haven't read this article before that. Only give knn solution and failed the interview.

0
Reply
Share
Report
ravimehtaq3432432234's avatar
Read More

A solution using MinHeap.. TC : O(nk*logk) SC : O(nk)

class Solution {

    public int minCostII(int[][] arr) {

        if (arr.length == 0) return 0;
        int k = arr[0].length;
        int n = arr.length;
        int[][] dp = new int[n][k]; 
        PriorityQueue<Integer> mnheap = new PriorityQueue<>();

     
        for (int color = 0; color < k; color++) {
            dp[0][color] = arr[0][color]; 
        }
        
        for (int house = 1; house < n; house++) {
            
            mnheap.clear();
            
            for (int color = 0; color < k; color++) {
                mnheap.add(dp[house-1][color]);
            }
                                    
            for (int color = 0; color < k; color++) {
              
                mnheap.remove(dp[house-1][color]);
                dp[house][color] = mnheap.peek() + arr[house][color];
                mnheap.add(dp[house-1][color]);
            }
        }
        
        int result = Integer.MAX_VALUE;
        
        for(int i = 0 ; i < k; i++) {
            result = Math.min(result, dp[n-1][i]);
        }
        
        return result;
    }
}

0
Reply
Share
Report
moraxu's avatar
Read More

In "Approach 4: Dynamic programming with Optimized Time", the time complexity is O(nk), because both inner loops have O(nk) so in total O(nk) + O(nk) = O(nk). But the first inner loop is O(nk) not O(k), as per the description.

0
Reply
Share
Report
wukongne's avatar
Read More

how about this?
'''
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:

    n, k = len(costs), len(costs[0])
    
    for i in range(1, n):
        for j in range(k):
            costs[i][j] = costs[i][j] + min(costs[i-1][0:j] + costs[i-1][j+1:])
            
    return min(costs[-1])

'''

0
Reply
Share
Report
ankit335's avatar
Read More

What is the runTime of this code below? I am confused if it is O(nk) or O(nk^2)

class Solution {
public int minCostII(int[][] costs) {
Integer[][] mem = new Integer[costs.length][costs[0].length];
return costHelper(costs, 0, -1, mem);
}

private int costHelper(int[][] costs, int house, int paintUsed, Integer[][] mem) {
    if (house >= costs.length) {
        return 0;
    }
    
    if (paintUsed != -1 && mem[house][paintUsed] != null) {
        return mem[house][paintUsed];
    }
    int minCost = Integer.MAX_VALUE;
    
    for (int i = 0; i < costs[0].length; i++) {
        if (i != paintUsed) {
            int colorCosts = costs[house][i];
            int remainingCosts = costHelper(costs, house + 1, i, mem);
            
            minCost = Math.min(minCost, colorCosts + remainingCosts);
        }
    }
    if (paintUsed != -1) {
        mem[house][paintUsed] = minCost;
    }
   
    return minCost;
}

}

0
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/02/2021 09:07Accepted16 ms10.9 MBcpp
06/02/2021 08:47Accepted32 ms11.4 MBcpp
06/02/2021 08:37Accepted12 ms10.9 MBcpp
06/02/2021 08:31Accepted28 ms11.7 MBcpp
265/1883
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
#251 Flatten 2D Vector
Medium
#252 Meeting Rooms
Easy
#253 Meeting Rooms II
Medium
#254 Factor Combinations
Medium
#255 Verify Preorder Sequence in Binary Search Tree
Medium
#256 Paint House
Medium
#257 Binary Tree Paths
Easy
#258 Add Digits
Easy
#259 3Sum Smaller
Medium
#260 Single Number III
Medium
#261 Graph Valid Tree
Medium
#262 Trips and Users
Hard
#263 Ugly Number
Easy
#264 Ugly Number II
Medium
#265 Paint House II
Hard
#266 Palindrome Permutation
Easy
#267 Palindrome Permutation II
Medium
#268 Missing Number
Easy
#269 Alien Dictionary
Hard
#270 Closest Binary Search Tree Value
Easy
#271 Encode and Decode Strings
Medium
#272 Closest Binary Search Tree Value II
Hard
#273 Integer to English Words
Hard
#274 H-Index
Medium
#275 H-Index II
Medium
#276 Paint Fence
Medium
#277 Find the Celebrity
Medium
#278 First Bad Version
Easy
#279 Perfect Squares
Medium
#280 Wiggle Sort
Medium
#281 Zigzag Iterator
Medium
#282 Expression Add Operators
Hard
#283 Move Zeroes
Easy
#284 Peeking Iterator
Medium
#285 Inorder Successor in BST
Medium
#286 Walls and Gates
Medium
#287 Find the Duplicate Number
Medium
#288 Unique Word Abbreviation
Medium
#289 Game of Life
Medium
#290 Word Pattern
Easy
#291 Word Pattern II
Medium
#292 Nim Game
Easy
#293 Flip Game
Easy
#294 Flip Game II
Medium
#295 Find Median from Data Stream
Hard
#296 Best Meeting Point
Hard
#297 Serialize and Deserialize Binary Tree
Hard
#298 Binary Tree Longest Consecutive Sequence
Medium
#299 Bulls and Cows
Medium
#300 Longest Increasing Subsequence
Medium